#pragma once

#include<string>
#include <memory>
#include<set>
#include<deque>
#include<vector>
#include <bitset>


class GameTree
{
    class Node;
    using node_ptr = std::shared_ptr<Node>;
    using node_father_ptr = std::weak_ptr<Node>;
private:

    class Node : std::enable_shared_from_this<Node>
    {
    public:
        int32_t value;
        uint32_t depth;
        node_father_ptr father;
        std::set<node_ptr> children; 
        int8_t cntX, cntY; // 记录当前棋局最后一步落子点的坐标

        std::vector<std::vector<int8_t>> board; // 记录当前棋局

    public:
        Node() 
            : value(INT32_MIN), depth(0), father(node_ptr(nullptr)), cntX(0), cntY(0), board(15, std::vector<int8_t>(15))
        {}

        Node(node_ptr node, int8_t opeX, int8_t opeY)
            : depth(node->depth + 1), father(node), cntX(opeX), cntY(opeY), board(node->board)
        {
            value = is_max_node() ? INT32_MIN : INT32_MAX;
            board[cntX][cntY] = (depth & 1u) ? 'B' : 'W';
        }

        bool is_max_node() { return (depth & 1u) ^ 1u; }

        

        // 评估函数
        void evaluate() {
            value = 0;
            // 检查所有可能连线
            for (int i = 0; i < 15; ++i) {
                for (int j = 0; j < 15; ++j) {
                    // 水平方向
                    if (j + 4 < 15) {
                        std::string s;
                        for (int8_t k = 0; k < 5; k++) s += convert(board[i][j + k]);
                        value += evaluate_black(s) - evaluate_white(s);
                    }
                    
                    // 垂直方向
                    if (i + 4 < 15) {
                        std::string s;
                        for (int8_t k = 0; k < 5; k++) s += convert(board[i + k][j]);
                        value += evaluate_black(s) - evaluate_white(s);
                    }
                    
                    // 对角线
                    if (i + 4 < 15 && j + 4 < 15) {
                        std::string s;
                        for (int8_t k = 0; k < 5; k++) s += convert(board[i + k][j + k]);
                        value += evaluate_black(s) - evaluate_white(s);
                    }
                    
                    // 反对角线
                    if (i + 4 < 15 && j - 4 >= 0) {
                        std::string s;
                        for (int8_t k = 0; k < 5; k++) s += convert(board[i + k][j - k]);
                        value += evaluate_black(s) - evaluate_white(s);
                    }
                }
            }
            
        }

    private:
        int32_t evaluate_black(std::string &s) {
            static std::string patterns[31] = {
                    "B0000", "0B000", "00B00", "000B0", "0000B",
                    "BB000", "0BB00", "00BB0", "000BB", "B0B00", "0B0B0", "00B0B", "B00B0", "0B00B", "B000B",
                    "BBB00", "0BBB0", "00BBB", "BB0B0", "0BB0B", "B0BB0", "0B0BB", "BB00B", "B00BB", "B0B0B",
                    "BBBB0", "BBB0B", "BB0BB", "B0BBB", "0BBBB", "BBBBB",
            };
            static int32_t scores[31] = {
                    1, 1, 1, 1, 1,
                    10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
                    100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
                    10000, 10000, 10000, 10000, 10000, 1000000,
            };
            for (int8_t i = 0; i < 31; i++)
                if (s == patterns[i]) return scores[i];
            return 0;
        }

        int32_t evaluate_white(std::string &s) {
            static std::string patterns[31] = {
                    "W0000", "0W000", "00W00", "000W0", "0000W",
                    "WW000", "0WW00", "00WW0", "000WW", "W0W00", "0W0W0", "00W0W", "W00W0", "0W00W", "W000W",
                    "WWW00", "0WWW0", "00WWW", "WW0W0", "0WW0W", "W0WW0", "0W0WW", "WW00W", "W00WW", "W0W0W",
                    "WWWW0", "WWW0W", "WW0WW", "W0WWW", "0WWWW", "WWWWW",
            };
            static int32_t scores[31] = {
                    1, 1, 1, 1, 1,
                    10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
                    1000, 2000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000,
                    100000, 100000, 100000, 100000, 100000, 10000000,
            };
            for (int8_t i = 0; i < 31; i++)
                if (s == patterns[i]) return scores[i];
            return 0;
        }

        std::string convert(int8_t pos) {
            if (pos == 0) return "0";
            if (pos == 'B') return "B"; else return "W";
        }
    };
    
    
private:
    int8_t expandRadius = 2;
    uint32_t maxDepth = 5;
    node_ptr nodeRoot;
    node_ptr nodeNext;
    std::deque<node_ptr> openTable;
    std::deque<node_ptr> closedTable;
    

public:
    GameTree()
        : expandRadius(2), maxDepth(5), nodeRoot(new Node), nodeNext(nullptr)
    {}

    explicit GameTree(uint32_t maxDepth, int8_t expandRadius) 
        : expandRadius(expandRadius), maxDepth(maxDepth), nodeRoot(new Node), nodeNext(nullptr)
    {}

    explicit GameTree(uint32_t maxDepth, int8_t expandRadius, std::vector<std::vector<int8_t>>& board) 
        : expandRadius(expandRadius), maxDepth(maxDepth), nodeRoot(new Node), nodeNext(nullptr)
    {
        nodeRoot->board = board;
    }



    std::vector<std::pair<int8_t, int8_t>> get_search_nodes(node_ptr node) {
        bool hasChess = false;
        std::vector<std::bitset<15>> newBoard(15);

        for (int8_t i = 0; i < 15; i++)
        {
            for (int8_t j = 0; j < 15; j++) 
            {
                if (node->board[i][j] == 0)
                    continue;
                
                hasChess = true;
                int8_t x1 = std::max(0, i - expandRadius), x2 = std::min(14, i + expandRadius);
                int8_t y1 = std::max(0, j - expandRadius), y2 = std::min(14, j + expandRadius);
                for (int8_t x = x1; x <= x2; x++)
                {
                    for (int8_t y = y1; y <= y2; y++)
                    {
                        if (node->board[x][y] == 0) 
                            newBoard[x][y] = true;
                    }
                }
            }
        }

        std::vector<std::pair<int8_t, int8_t>> mask;

        // 如果没有棋子，就在7，7的位置放黑色棋子
        if (!hasChess) {
            mask.emplace_back(std::pair<int8_t, int8_t>(7, 7));
        } else {
        
            for (int8_t i = 0; i < 15; i++)
                for (int8_t j = 0; j < 15; j++)
                    if (newBoard[i][j])
                        mask.emplace_back(std::pair<int8_t, int8_t>(i, j));
        }

        return mask;
    }

    int8_t expand_children_nodes(node_ptr node) {
        std::vector<std::pair<int8_t, int8_t>> mask = get_search_nodes(node);
        for (auto pos : mask) {

            node_ptr n(new Node(node, pos.first, pos.second));
            node->children.insert(n);
            openTable.push_front(n);
        }
        return mask.size();
    }

    static bool is_alpha_beta_cut(node_ptr node) {
        if (node == nullptr || node->father.lock() == nullptr) return false;
        if (node->is_max_node() && node->value > node->father.lock()->value) return true;
        if (!node->is_max_node() && node->value < node->father.lock()->value) return true;
        return is_alpha_beta_cut(node->father.lock());
    }

    static void update_value_from_node(node_ptr node) {
        if (node == nullptr) return;
        if (node->children.empty()) 
        {
            update_value_from_node(node->father.lock());
            return;
        }
        if (node->is_max_node()) 
        {
            int32_t cntValue = INT32_MIN;
            for (node_ptr n : node->children)
                if (n->value != INT32_MAX) cntValue = std::max(cntValue, n->value);
            if (cntValue > node->value) {
                node->value = cntValue;
                update_value_from_node(node->father.lock());
            }
        } 
        else 
        {
            int32_t cntValue = INT32_MAX;
            for (node_ptr n : node->children)
                if (n->value != INT32_MIN) cntValue = std::min(cntValue, n->value);
            if (cntValue < node->value) {
                node->value = cntValue;
                update_value_from_node(node->father.lock());
            }
        }
    }

    void set_next_pos() {
        nodeNext = *nodeRoot->children.begin();
        for (node_ptr n : nodeRoot->children)
            if (n->value > nodeNext->value) nodeNext = n;
    }

    std::pair<int8_t, int8_t> get_next_pos() {
        if (nodeNext == nullptr)
            return std::pair<int8_t, int8_t>(255, 255);
        else
            return std::pair<int8_t, int8_t>(nodeNext->cntX, nodeNext->cntY);
    }

    int8_t game() {
        int8_t result = board_identify(nodeRoot->board);
        if (result != 0) return result;

        openTable.push_back(nodeRoot);
        while (!openTable.empty()) {
            node_ptr node = openTable.front();
            openTable.pop_front();
            closedTable.push_back(node);
            if (is_alpha_beta_cut(node->father.lock())) continue;
            if (node->depth < maxDepth) {
                if (expand_children_nodes(node) != 0) {
                    continue;  // 优先处理子节点
                }
            }
            node->evaluate();
            update_value_from_node(node);
        }

        set_next_pos();
        return 0;
    }

    static int8_t board_identify(std::vector<std::vector<int8_t>>& board);

};

int8_t GameTree::board_identify(std::vector<std::vector<int8_t>>& board) {
    for (int8_t i = 0; i < 15; i++)
        for (int8_t j = 0; j < 15; j++) {
            if (board[i][j] == 0) continue;

            // 水平方向
            if (j + 4 < 15) {
                int count = 1;
                for (int k = 1; k < 5; ++k)
                    if (board[i][j+k] == board[i][j]) ++count;
                if (count == 5)
                {
                    return board[i][j] == 'W' ? 'W' : 'B';
                }
            }
            
            // 垂直方向
            if (i + 4 < 15) {
                int count = 1;
                for (int k = 1; k < 5; ++k)
                    if (board[i+k][j] == board[i][j]) ++count;
                if (count == 5)
                {
                    return board[i][j] == 'W' ? 'W' : 'B';
                }
            }
            
            // 对角线
            if (i + 4 < 15 && j + 4 < 15) {
                int count = 1;
                for (int k = 1; k < 5; ++k)
                    if (board[i+k][j+k] == board[i][j]) ++count;
                if (count == 5)
                {
                    return board[i][j] == 'W' ? 'W' : 'B';
                }
            }
            
            // 反对角线
            if (i + 4 < 15 && j - 4 >= 0) {
                int count = 1;
                for (int k = 1; k < 5; ++k)
                    if (board[i+k][j-k] == board[i][j]) ++count;
                if (count == 5)
                {
                    return board[i][j] == 'W' ? 'W' : 'B';
                }
            }
        }
    return 0;
}